package com.cjm.algorithm.leetcode;

import com.cjm.algorithm.TreeNode;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @see <a href=https://leetcode.cn/problems/path-sum-iii/>路径总和 III</a>
 */
public class PathSum437 {

    public static int pathSum2(TreeNode root, int targetSum) {
        if (root == null) return 0;
        int res = findPath2(root, targetSum);
        res += pathSum2(root.left, targetSum);
        res += pathSum2(root.right, targetSum);
        return res;
    }

    private static int findPath2(TreeNode root, int targetSum) {
        if (root == null) return 0;
        int res = 0;
        if (root.val == targetSum) {
            res++;
        }
        res +=findPath2(root.left, targetSum - root.val);
        res +=findPath2(root.right, targetSum - root.val);
        return res;
    }

    public static int pathSum1(TreeNode root, int targetSum) {
        if (root == null) return 0;
        int res = findPath1(root, targetSum);
        res += pathSum1(root.left, targetSum);
        res += pathSum1(root.right, targetSum);
        return res;
    }

    private static int findPath1(TreeNode root, int targetSum) {
        if (root == null) return 0;
        int res = 0;
        if (root.val == targetSum) {
            res++;
        }
        res += findPath1(root.left, targetSum - root.val);
        res += findPath1(root.right, targetSum - root.val);
        return res;
    }

    public static int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        Queue<Integer> queue = new LinkedList<>();
        return count(root, targetSum, 0, queue);
    }

    private static int count(TreeNode root, int targetSum, int cur, Queue<Integer> queue) {
        if (root == null) {
            return 0;
        }
        int count = 0;
        Integer peek = queue.peek();
        if (!queue.isEmpty() && peek == 0) {
            count++;
        }
        int curval = root.val;
        if (((cur + curval > targetSum)) || ((cur + curval) < targetSum && targetSum < 0)) {
            cur = cur + curval;
            while (!queue.isEmpty() && ((cur > targetSum || (targetSum < 0 && cur < targetSum)))) {
                cur = cur - queue.poll();
            }
        } else {
            cur = cur + curval;
        }
        if (cur == targetSum) {
            count++;
        }
        Queue<Integer> left = new LinkedList<>(queue);
        left.add(curval);
        int leftres = count(root.left, targetSum, cur, left);
        Queue<Integer> right = new LinkedList<>(queue);
        right.add(curval);
        int rightres = count(root.right, targetSum, cur, right);
        return leftres + rightres + count;
    }

    public static void main(String[] args) {
        System.err.println(pathSum(TreeNode.generatorTreeNode(new Integer[]{10, 5, -3, 3, 2, null, 11, 3, -2, null, 1}), 8));
        System.err.println(pathSum(TreeNode.generatorTreeNode(new Integer[]{5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1}), 22));
        System.err.println(pathSum(TreeNode.generatorTreeNode(new Integer[]{-2, null, -3}), -3));
        System.err.println(pathSum(TreeNode.generatorTreeNode(new Integer[]{0, 1, 1}), 1));
    }
}
